#include "maximalSquare.h"
int maximalSquare(std::vector<std::vector<char>> &matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    std::vector<std::vector<int>> dp =
        std::vector<std::vector<int>>(rows, std::vector<int>(cols, 0));
    int max_edge = 0;
    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < cols; col++) {
            if (row == 0 && col == 0)
                dp[row][col] = matrix[row][col] == '1' ? 1 : 0;
            else if (row != 0 && col == 0)
                dp[row][col] = matrix[row][col] == '1'
                                   ? std::min(dp[row - 1][col], 0) + 1
                                   : 0;
            else if (row == 0 && cols != 0)
                dp[row][col] = matrix[row][col] == '1'
                                   ? std::min(dp[row][col - 1], 0) + 1
                                   : 0;
            else {

                dp[row][col] =
                    matrix[row][col] == '1'
                        ? std::min(std::min(dp[row - 1][col], dp[row][col - 1]),
                                   dp[row - 1][col - 1]) +
                              1
                        : 0;
            }
            max_edge = std::max(max_edge, dp[row][col]);
        }
    }
    return max_edge * max_edge;
}
